package com.ruijixiang.leetcode.weekly.leetcode2024.leetcode20241013;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class leetcode3318 {

    /**
     * 计算子数组的x-sum
     * @param nums
     * @param k
     * @param x
     * @return
     */
    public int[] findXSum(int[] nums,int k,int x){
        int n=nums.length;
        int[] result=new int[n-k+1];
        // 1、
        Map<Integer,Integer> map=new HashMap<>();
        // 2、
        PriorityQueue<Integer> queue=new PriorityQueue<>((a,b)->map.get(a).equals(map.get(b)) ? b-a : -(map.get(a)-map.get(b)));// 比较器构建小堆顶
        // 3、
        for(int j=0;j<result.length;j++){
            for(int i=j;i<k+j;i++){
                map.put(nums[i],map.getOrDefault(nums[i],0)+1);
            }
            for(int i=j;i<k+j;i++){
                if(queue.contains(nums[i])){
                    continue;
                }
                queue.add(nums[i]);
            }
            result[j]=sumTopX(map,queue,x);
            map.clear();
            queue.clear();
        }
        return result;
    }

    // 计算x-sum
    private int sumTopX(Map<Integer,Integer> map,PriorityQueue<Integer> queue,int x){
        int sum=0;
        while(!queue.isEmpty() && x>0){
            int num=queue.poll();
            sum+=map.get(num)*num;
            x--;
        }
        return sum;
    }
}
